package com.cb2.algorithm.leetcode;

/**
 * <a href='https://leetcode.cn/problems/house-robber/'>打家劫舍(House Robber)</a>
 * <p>你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，<b>如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警</b>。</p>
 * <p>给定一个代表每个房屋存放金额的非负整数数组，计算你<b>不触动警报装置的情况下</b> ，一夜之内能够偷窃到的最高金额。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *  示例 1：
 *      输入：[1,2,3,1]
 *      输出：4
 *      解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
 *          偷窃到的最高金额 = 1 + 3 = 4 。
 *
 *  示例 2：
 *      输入：[2,7,9,3,1]
 *      输出：12
 *      解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
 *          偷窃到的最高金额 = 2 + 9 + 1 = 12 。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>1 <= nums.length <= 100</li>
 *     <li>0 <= nums[i] <= 400</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2025/4/1 11:33
 */
public class LC0198HouseRobber_M {
    static class Solution {
        public int rob(int[] nums) {
            int ret = 0;
            int[] cache = new int[nums.length];
            // 1.选择偷取当前房屋
            int i1 = nums[0] + rob(nums, 2,cache);
            // 2.选择不偷取当前房屋
            int i2 = rob(nums, 1,cache);
            ret = Math.max(ret, Math.max(i1, i2));
            return ret;
        }

        private int rob(int[] nums, int start,int[] cache) {
            if (start >= nums.length) {
                return 0;
            }
            int ret = 0;
            for (int i = start; i < nums.length; i++) {
                // 1.选择偷取当前房屋
                int i1;
                if (cache[i] != 0) {
                    i1 = cache[i];
                } else {
                    i1 = nums[i] + rob(nums, i + 2, cache);
                    cache[i] = i1;
                }
                // 2.选择不偷取当前房屋
                int i2 = rob(nums, i + 1, cache);
                ret = Math.max(ret, Math.max(i1, i2));
            }
            return ret;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.rob(new int[]{1, 2, 3, 1}));
        System.out.println(solution.rob(new int[]{2, 7, 9, 3, 1}));
        System.out.println(solution.rob(new int[]{183,219,57,193,94,233,202,154,65,240,97,234,100,249,186,66,90,238,168,128,177,235,50,81,185,165,217,207,88,80,112,78,135,62,228,247,211}));
    }
}
